1. Field of the Invention
Embodiments relate to searching the memory of processor-based devices.
2. Background Art
Search efficiency is crucial for many computing functions including for packet processing in network devices, such as bridges, switches, routers, gateways, network proxies, network load balancing devices, and network security devices. One or more searches are performed for each packet at each hop along a network path, based upon the respective headers, to determine, for example, a next hop to which the packet is to be forwarded and/or to determine whether the packet can be forwarded based upon access control rules.
As computer networks grow, scalability issues arise with respect to search efficiency, search table size, and power consumption. Search tables generally increase in size with the growth in network size. As search tables grow, their power consumption may also increase because some types of search tables, such as tables implemented in content addressable memory (CAM), consume large amounts of power.
CAM-based lookup tables are frequently used for fast search operation. Many network devices, such as those noted above, use a CAM or a ternary CAM (TCAM) for routing based upon a longest prefix match of network IP addresses and for access control list (ACLs) lookup operations.
A CAM enables comparing an input search expression (e.g., search key) to a plurality of stored entries simultaneously. Thus, determining one or more matching entries in a CAM is substantially faster than in memories such as random access memory (RAM) which are accessed using memory addresses. A TCAM provides the same ability to compare the search key simultaneously to multiple stored data entries as a CAM, and in addition enables some fields to be marked as “don't care” or wildcards, effectively allowing those fields to match any value in the corresponding field of the search key. However, although CAMs and TCAMs are fast, they consume large amounts of power relative to other types of memory. The size of a CAM or TCAM directly affects the power consumption associated with that memory.
In order to address the ongoing growth of search table size, requirements for reduced power consumption, and faster packet forwarding, systems and methods are desired for more efficient use of CAM and other memory resources for lookup operations.